package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-06
 */

/**
 * 给你一棵以root为根的二叉树和一个head为第一个节点的链表。
 *
 * 如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以head为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
 *
 * 一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
 */
public class leetcode1367 {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root==null) return false;
        return search(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
    }
    public boolean search(ListNode head,TreeNode root){
        if (head==null) return true;
        if (root==null) return false;

        if (root.val!=head.val) return false;
        return search(head.next,root.left) || search(head.next,root.right);
    }
}
